package de.cube3d.blitwit.space 
{
	import flash.geom.Rectangle;
	
	/**
	 * The gridspace is a very efficient structure for storing large amounts of sprites that are each
	 * of almost equal sizes (factor of 1:10 is ok, e.g. lots of sprites with 10 to 100 pixels in 
	 * width / height). 
	 * 
	 * In principal, it is just one array of arrays and queries are looking into each cell that
	 * is being intersected by the query. It can be a structure that is very fast and very efficient
	 * in memory usage. But it is also a structure where you can do quite a few things wrong...
	 * 
	 * The point is that YOU must provide the number of x and y divisions for the grid
	 * to be used. You should chose the division count on the following criterias:
	 *  - the cells should be sized around the average size of your sprites
	 *  - the cells shouldn't be much smaller than your expected screen size (e.g. 100x100 cells on a 800x600 
	 *		pixel area is going to be really slow)
	 *  - the number of cells should be reasonably, keep in mind that the number of cells in your grid
	 * 		is x*y, so if you have 100 cells in x and y each, the array will have 10k entries (which is ok).
	 * 
	 * There are three mistakes you can do when using this space:
	 *  1. Choosing a grid that is too small: Inserts / removes will be consuming as well as range queries
	 * 		across the cells
	 *  2. Choosing a grid that is too large: Range queries will take much longer, resulting in slow drawing
	 *  3. Sizes of sprites vary heavily: In that case, the small sprites will clutter the grid cell's lists
	 * 		or the large sprites inserts / removes will have to touch too many cells and range queries
	 * 		will be facing the same (large) elements again and again (though it won't do rectangle 
	 * 		intersections after the first test, it'll still need to skip these elements).
	 * 
	 * A minor mistake can be to use a grid that is huge but most cells are empty. It's quite memory inefficent
	 * then and you might want to pick the BTSpace instead then.
	 * 
	 * If you are unsure about your situation or don't deal with many sprites (<~50k), you can just use
	 * the BTSpace class, it's less efficient and also more memory consuming (well, depends), but it's much
	 * harder to screw that binary tree up by making wrong choices.
	 */
	public class GridSpace extends Space
	{
		private var _grid:Vector.<Vector.<GridSpaceContainer>>;
		private var _cellWidth:Number;
		private var _cellHeight:Number;
		private var _ydivCnt:int;
		private var _xdivCnt:int;
		
		/**
		 * Creates a grid based on the given parameters. Will create an array of xdivCnt * ydivCnt size.
		 * 
		 * @param	x
		 * @param	y
		 * @param	width
		 * @param	height
		 * @param	xdivCnt
		 * @param	ydivCnt
		 */
		public function GridSpace(x:Number,y:Number,width:Number,height:Number,xdivCnt:int,ydivCnt:int) 
		{
			super(x, y, width, height);
			_grid = new Vector.<Vector.<GridSpaceContainer>>(xdivCnt * ydivCnt, true);
			for (var i:int = _grid.length - 1; i >= 0; i -= 1) {
				_grid[i] = new Vector.<GridSpaceContainer>();
			}
			_cellHeight = height / ydivCnt;
			_cellWidth = width / xdivCnt;
			_xdivCnt = xdivCnt;
			_ydivCnt = ydivCnt;
		}
		
		private static var x1:int, y1:int, x2:int, y2:int;
		private function calcrange (x:Number, y:Number, width:Number, height:Number):void {
			// using this in three cases and I hate c&p
			x1 = Math.floor(Math.max(0, (x - area.x) / _cellWidth));
			y1 = Math.floor(Math.max(0, (y - area.y) / _cellHeight));
			x2 = Math.ceil(Math.min(_xdivCnt - 1, (x - area.x + width) / _cellWidth));
			y2 = Math.ceil(Math.min(_ydivCnt - 1, (y - area.y + height) / _cellHeight));
		}
		
		override protected function _internalAdd (bs:SpaceObject):Boolean 
		{
			calcrange(bs.x, bs.y, bs.width, bs.height);
			return _add(bs);
		}
		
		private function _add(bs:SpaceObject):Boolean {
			var container:GridSpaceContainer = new GridSpaceContainer(bs);
			for (var j:int = y1; j <= y2; j += 1) {
				var idx:int = x1 + j * _xdivCnt;
				for (var i:int = x1; i <= x2; i += 1,idx+=1) {
					_grid[idx].push(container);
				}
			}
			return true;
		}
		
		private var _marker:int = 0;
		override public function enlistContent(range:Rectangle, appendTo:Vector.<SpaceObject>):Vector.<SpaceObject> 
		{
			calcrange(range.x, range.y, range.width, range.height);
			var mark:int = ++_marker;
			
			for (var j:int = y1; j <= y2; j += 1) {
				var idx:int = x1 + j * _xdivCnt;
				for (var i:int = x1; i <= x2; i += 1, idx += 1) {
					for each (var container:GridSpaceContainer in _grid[idx]) {
						if (container._marker == mark) continue;
						container._marker = mark;
						if (container._obj.intersects(range))
							appendTo.push(container._obj);
					}
				}
			}
			return appendTo;
		}
		
		override public function getObjectsAt(x:Number, y:Number, appendTo:Vector.<SpaceObject>):Vector.<SpaceObject> 
		{
			x1 = Math.floor(Math.max(0, (x - area.x) / _cellWidth));
			y1 = Math.floor(Math.max(0, (y - area.y) / _cellHeight));
			for each (var container:GridSpaceContainer in _grid[x1 + y1 * _xdivCnt]) {
				if (container._obj.contains(x, y)) 
					appendTo.push(container._obj);
			}
			return appendTo;
		}
		
		override protected function _internalRemove (bs:SpaceObject):Boolean 
		{
			calcrange(bs.x, bs.y, bs.width, bs.height);
			return _rm(bs);
		}
		
		private function _rm (bs:SpaceObject):Boolean {
			var container:GridSpaceContainer = null;
			for (var j:int = y1; j <= y2; j += 1) {
				var idx:int = x1 + j * _xdivCnt;
				for (var i:int = x1; i <= x2; i += 1, idx += 1) {
					var rm:int = -1;
					if (container) rm = _grid[idx].indexOf(container);
					else {
						for (var k:int = _grid[idx].length - 1; k >= 0; k -= 1) {
							if ((container = _grid[idx][k])._obj == bs) {
								rm = k;
								break;
							}
						}
					}
					if (rm >= 0) _grid[idx].splice(rm, 1);
				}
			}
			
			return container != null;
		}
		
		override public function objectMoved(obj:SpaceObject, oldx:Number, oldy:Number, newx:Number, newy:Number):Space 
		{
			calcrange(oldx, oldy, obj.width, obj.height);
			_rm(obj);
			calcrange(newx, newy, obj.width, obj.height);
			_add(obj);
			if (owner) {
				owner.markArea(oldx, oldy, obj.width, obj.height).markArea(newx, newy, obj.width, obj.height);
			}
			return this;
		}
	}

}